//
// Created by liushuai on 2020/5/5.
//
#include "dfs_tree.h"

#include <vector>

void dfs_tree_stack(TreeNode* root) {
  std::stack<TreeNode*> s;
  TreeNode* current_node = root;
  s.push(root);
  while (current_node) {
    TreeNode* pop_node = current_node;
    if (s.size() > 0) s.pop();
    std::cout << "访问节点:" << pop_node->val;
    if (pop_node->right) s.push(pop_node->right);
    if (pop_node->left) s.push(pop_node->left);
    if (s.size() > 0)
      current_node = s.top();
    else
      current_node = nullptr;
  }
}

void dfs_travel_layer(TreeNode* root, int layer,
                      std::vector<std::vector<int>>& result) {
  if (root) {
    // 不能直接push_back，通过判断result的大小获取层数否则层result的size可能会大于层数
    if (result.size() < layer + 1) result.push_back(std::vector<int>());
    result.at(layer).push_back(root->val);
    dfs_travel_layer(root->left, layer + 1, result);
    dfs_travel_layer(root->right, layer + 1, result);
  }
}
std::vector<std::vector<int>> dfs_travel_layer(TreeNode* root) {
  std::vector<std::vector<int>> result;
  dfs_travel_layer(root, 0, result);
  return result;
}
